package j2024.j202409;

import java.util.ArrayList;
import java.util.List;

public class j0921 {
    /**
     * 68. 文本左右对齐
     * 给定一个单词数组 words 和一个长度 maxWidth ，
     * 重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
     *
     * 你应该使用 “贪心算法” 来放置给定的单词；
     * 也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
     *
     * 要求尽可能均匀分配单词间的空格数量。
     * 如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
     *
     * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
     * @param words
     * @param maxWidth
     * @return
     */
    //模拟
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ret = new ArrayList<>();
        int n = words.length,right = 0;
        while(true){
            int left = right;
            int wordlen = 0;
            while(right<n && (wordlen+words[right].length()+right-left)<=maxWidth){
                wordlen+=words[right++].length();
            }
            //判断当前行是最后一行
            if(right==n){
                StringBuilder tmp = new StringBuilder();
                int count = 0;
                //最后一个单词不加空格
                for (int i = left; i < right-1; i++) {
                    tmp.append(words[i]);
                    tmp.append(' ');
                    count+=1+words[i].length();
                }
                tmp.append(words[right-1]);
                count+=words[right-1].length();
                for (int i = count; i < maxWidth; i++) {
                    tmp.append(' ');
                }
                ret.add(tmp.toString());
                return ret;
            }
            //单词数
            int couWords = right-left;
            //空格数
            int spaces = maxWidth-wordlen;

            //当前行只有一个单词
            if(couWords==1){
                StringBuilder tmp = new StringBuilder();
                tmp.append(words[left]);
                for (int i = 0; i < spaces; i++) {
                    tmp.append(' ');
                }
                ret.add(tmp.toString());
                continue;
            }

            //当前行不只有一个单词
            if(couWords!=1){
                StringBuilder tmp = new StringBuilder();
                int aver = spaces/(couWords-1);
                int prev = spaces%(couWords-1);
                int cou = 0;
                for (int i = left; i < right-1; i++) {
                    tmp.append(words[i]);
                    if(cou<prev){
                        for (int j = 0; j < aver+1; j++) {
                            tmp.append(' ');
                        }
                        cou++;
                    }else {
                        for (int j = 0; j < aver; j++) {
                            tmp.append(' ');
                        }
                    }
                }
                tmp.append(words[right-1]);
                ret.add(tmp.toString());
            }
        }
    }

    /**
     * 125. 验证回文串
     * 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。
     * 则可以认为该短语是一个 回文串 。
     *
     * 字母和数字都属于字母数字字符。
     *
     * 给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
     * @param s
     * @return
     */
    //双指针
    public boolean isPalindrome(String s) {
        int n = s.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if((s.charAt(i)>='a'&&s.charAt(i)<='z') || (s.charAt(i)>='A'&&s.charAt(i)<='Z')||(s.charAt(i)>='0'&&s.charAt(i)<='9')){
                sb.append(s.charAt(i));
            }
        }
        char[] str = sb.toString().toLowerCase().toCharArray();
        if(str.length==0||str.length==1){
            return true;
        }
        int m = str.length;
        int left = 0,right = m-1;
        while(left<right){
            if(str[left]!=str[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    public boolean isPalindrome2(String s) {
        //正则表达式
        s = s.replaceAll("[^a-zA-Z0-9]","").toLowerCase();

        int n = s.length();
        int left = 0,right = n-1;
        while(left<right){
            if(s.charAt(left)!=s.charAt(right)){
                return false;
            }
            left++;right--;
        }
        return true;
    }

    /**
     * 392. 判断子序列
     * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
     *
     * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
     * （例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
     *
     * 进阶：
     *
     * 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。
     * 在这种情况下，你会怎样改变代码？
     * @param s
     * @param t
     * @return
     */
    public boolean isSubsequence(String s, String t) {
        int n = s.length();
        int m = t.length();
        int si = 0,ti = 0;
        while(si<n && ti<m){
            if(s.charAt(si)==t.charAt(ti)){
                si++;ti++;
            }else {
                ti++;
            }
        }
        return si>n-1;
    }
}
